#pragma once
#include<vector>

using namespace std;

template<typename Comparable>
void FAFBSort(vector<Comparable>& _data,int StartIndex,int LastIndex)
{
	if (StartIndex < LastIndex)
	{
		srand(unsigned(time(NULL)));

		int randNum = rand() % (LastIndex - StartIndex) + StartIndex;

		int i = StartIndex;
		int j = LastIndex;
		Comparable Pivot = _data[randNum];


		//Find Pivot Location
		while (i < j)
		{
			//backward to find smaller,backward when bigger
			while (i < j && _data[j] > Pivot)
				j--;
			if (i < j)
				_data[i] = _data[j];


			//forward to find bigger,forward when smaller
			while (i < j && _data[i] <= Pivot)
				i++;
			if (i < j)
				_data[j] = _data[i];
		}

		//Setup Pivot location value
		_data[i] = Pivot;

		//Front Part
		FAFBSort(_data,StartIndex,i - 1);

		//Back Part
		FAFBSort(_data,j + 1,LastIndex);
	}
}




template<typename Comparable>
void InsertSort( vector<Comparable>& _data )
{
	for (int j = 1; j < _data.size(); j++)
	{
		//Dig Hole
		Comparable Key = _data[j];
		int i = j - 1;
		
		//move forward all value that greater than key
		//break when find value smaller than Key
		while (i >= 0 && _data[i] > Key)
		{
			_data[i + 1] = _data[i];
			
			//New Hole
			i--;
		}

		//Put Key back into Hole
		_data[i + 1] = Key;
	}
}

template<typename Comparable>
void Sort( vector<Comparable>& _data )
{
	if (_data.size() <= 1)
		return;
	else if (_data.size() >= 10)
	{
		FAFBSort( _data, 0, _data.size() - 1 );
	}
	else
	{
		InsertSort(_data);
	}
	
}